1776B - Vittorio Plays with LEGO Bricks - CodeForces Solution

// Problem: B. Vittorio Plays with LEGO Bricks
// Contest: Codeforces - SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
// URL: https://codeforces.com/contest/1776/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define bit(x) (1LL << (x))
#define lowbit(x) (x & (-x))
#define SQU(x) ((x) * (x))
#define ls id << 1
#define rs id << 1 | 1
//#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int inv2 = (mod + 1) / 2;
ll qpow(ll x,ll y) {
    ll res = 1;
    while(y) {
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
void add(int &x,int y) {
    x += y;
    if(x >= mod) x -= mod;
}
const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
void solve() {
	ll n,m;cin >> n >> m;
	vector <ll> a(n + 1);
	for(int i = 1;i <= n;i++) cin >> a[i];
	vector <vector <ll>> f(n + 1,vector <ll> (n + 1,1LL << 60));
	for(int i = 1;i <= n;i++) f[i][i] = m;
	for(int len = 2;len <= n;len++) {
		for(int i = 1;i + len - 1 <= n;i++) {
			int j = i + len - 1;
			int les = max(0LL,m - (a[j] - a[i] - 1) / 2);
			for(int k = i;k < j;k++) f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] - les);
		}
	}
	cout << f[1][n] << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(20);
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int T = 1;
//    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}
/*
*/